package leetcode.offer0114;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public String alienOrder(String[] words) {
		// ["wrt","wrf","er","ett","rftt"]
		int len = words.length;
		Integer[] ins = new Integer[26];
		List<Set<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i < ins.length; i++) {
			nexts.add(new HashSet<>());
		}
		for (int i = 0; i < len; i++) {
			char[] cs1 = words[i].toCharArray();
			for (char c : cs1) {
				int index = c - 'a';
				if (ins[index] == null) {
					ins[c - 'a'] = 0;
				}
			}
			for (int j = 0; j < i; j++) {
				char[] cs2 = words[j].toCharArray();
				boolean ok = true;
				for (int k = 0; k < Math.min(cs1.length, cs2.length); k++) {
					if (cs1[k] != cs2[k]) {
						int big = cs1[k] - 'a';
						int small = cs2[k] - 'a';
						if (!nexts.get(big).contains(small)) {
							ins[small]++;
							nexts.get(big).add(small);
						}
						ok = false;
						break;
					}
				}
				if (ok && cs2.length > cs1.length) {
					return "";
				}
			}
		}
		int size = 0;
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < ins.length; i++) {
			Integer index = ins[i];
			if (index != null) {
				size++;
				if (index == 0) {
					queue.add(i);
				}
			}
		}
		char[] ans = new char[size];
		while (!queue.isEmpty()) {
			int index = queue.poll();
			ans[--size] = (char) (index + 'a');
			Set<Integer> next = nexts.get(index);
			for (int n : next) {
				if (--ins[n] == 0) {
					queue.add(n);
				}
			}
		}
		return size == 0 ? new String(ans) : "";
	}

	@Override
	public void debug4() {
		H.compare("", this.alienOrder(H.str2array2("[\"abc\",\"ab\"]")));
		H.compare("wertf", this.alienOrder(H.str2array2("[\"wrt\",\"wrf\",\"er\",\"ett\",\"rftt\"]")));
		H.compare("yzx", this.alienOrder(H.str2array2("[\"zy\",\"zx\"]")));
//		H.compare("yxz", this.alienOrder(H.str2array2("[\"zy\",\"zx\"]")));
		H.compare("zx", this.alienOrder(H.str2array2("[\"z\",\"x\"]")));
		H.compare("", this.alienOrder(H.str2array2("[\"z\",\"x\",\"z\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	private List<Integer>[] group(int[] nums) {
		int arraySize = 1;
		List<Integer>[] indexs = new ArrayList[arraySize];
		for (int i = 0; i < arraySize; i++) {
			indexs[i] = new ArrayList<>();
		}
		for (int i = 0; i < nums.length; i++) {
			indexs[nums[i]].add(i);
		}
		return indexs;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
